/**
 * 
 */
package graph;

import io.ConfReader;
import io.Data;
import io.DataReader;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Set;
import java.util.StringTokenizer;

import org.apache.commons.collections15.CollectionUtils;

import route.Route;
import rtree.RTree;
import rtree.RTreeUtil;
import spatialindex.IData;
import spatialindex.IEntry;
import spatialindex.INode;
import spatialindex.IQueryStrategy;
import spatialindex.ISpatialIndex;
import spatialindex.IVisitor;
import spatialindex.Point;
import spatialindex.Region;
import storagemanager.IBuffer;
import storagemanager.IStorageManager;
import storagemanager.MemoryStorageManager;
import storagemanager.PropertySet;
import storagemanager.RandomEvictionsBuffer;
import util.Sequencer;
import util.Statistics;

import algo.Share;

import com.vividsolutions.jts.geom.Coordinate;
import com.vividsolutions.jts.geom.LineSegment;

import edu.uci.ics.jung.graph.DirectedSparseMultigraph;
import edu.uci.ics.jung.graph.Graph;
import edu.uci.ics.jung.graph.UndirectedSparseGraph;
import exception.InvalidArgumentException;
import facility.Facility;

/**
 * 
 * @author xiaohui
 * 
 *         2011-11-23: added configuration and statistics <br>
 *         2011-11-28 remove function to do map-matching <br>
 *         2011-11-28: remove routes RTree <br>
 *         TODO Augmentation needs to merge adjacent smaller edges <br>
 *         TODO Iterative method needs to extend to the full length <br>
 * 
 */
public class Network {
	Data data;

	private static String vertexFile = "D:/jung/nodes.txt";
	private static String edgeFile = "D:/jung/edges.txt";
	private static String facilityFile = "D:/jung/facility.txt";
	private static String routesFile = "D:/jung/routes.txt";;
	private static int numRoutesToRead = 2500;
	private static int numFacilitiesToRead = 1600;

	int numTrials = 3;
	static double delta = 0.5;
	static int edgeCounter = 0;
	static int vertexCounter = 0;
	private static final int AUG = 1;
	private static final int ITERATIVE = 2;

	private static final int X = 0;
	private static final int Y = 1;
	static Statistics stats = new Statistics();

	/**
	 * entry point
	 * 
	 * @param args
	 * @throws Exception
	 */
	public static void main(String[] args) throws Exception {

		ConfReader reader = new ConfReader();
		HashMap<String, String> conf = reader.readConfFile(args[0]);

		// RTreeUtil rtreeUtil = new RTreeUtil();

		delta = Double.parseDouble(conf.get("delta"));

		BufferedWriter bw = new BufferedWriter(new FileWriter(
				conf.get("outFile")));
		vertexFile = conf.get("nodesFile");
		edgeFile = conf.get("edgesFile");
		facilityFile = conf.get("facilitiesFile");
		routesFile = conf.get("routesFile");
		stats.delta = delta;
		numRoutesToRead = Integer.parseInt(conf.get("numRoutesToRead"));
		numFacilitiesToRead = Integer.parseInt(conf.get("numFacilitiesToRead"));

		Network network = new Network();

		if (Integer.parseInt(conf.get("func")) == AUG) {

			System.out
					.println("===============Augment Graph to Find Optimal Segment==================");
			bw.write("Graph Augmentation=====");
			bw.newLine();
			long ps = System.currentTimeMillis();
			List<GraphEdge> optSegs = network.findOptSegsAug();

			long pe = System.currentTimeMillis();
			stats.elapsedTime = (pe - ps) / 1000.0; // second
			writeConf(conf, bw);
			stats.toFile(bw);

			bw.write("========Result===========");
			bw.newLine();
			writeList(bw, optSegs);

		} else if (Integer.parseInt(conf.get("func")) == ITERATIVE) {
			System.out
					.println("===============Iterative Partition to Find Optimal Segment==================");
			bw.write("===========Iterative Partitioning=====");
			bw.newLine();
			long ps = System.currentTimeMillis();
			List<SplitableSegment> optSegsIterative = network
					.findOptSegsIterative();

			long pe = System.currentTimeMillis();
			stats.elapsedTime = (pe - ps) / 1000.0; // second

			writeConf(conf, bw);
			stats.toFile(bw);
			bw.write("========Result===========");
			bw.newLine();
			writeList(bw, optSegsIterative);

		} else {
			throw new InvalidArgumentException("function number is not valid");
		}

		bw.close();
		System.out.println("Check out result file: " + conf.get("outFile"));
	}

	private static void writeConf(HashMap<String, String> conf,
			BufferedWriter bw) throws IOException {
		for (String key : conf.keySet()) {
			bw.write(key + "=>" + conf.get(key));
			bw.newLine();
		}
	}

	private static void writeList(BufferedWriter bw, List list)
			throws Exception {
		for (Object o : list) {
			bw.write(o.toString());
			bw.newLine();
		}
	}

	/**
	 * Algorithm 1: find optimal segments with graph augmentation handle edges
	 * with equal scores
	 * 
	 * @param graph
	 * @return the list of road segments with highest scores
	 * @throws Exception
	 */
	List<GraphEdge> findOptSegsAug() throws Exception {
		long ls = System.currentTimeMillis();
		// loading network graph
		System.out.println("loading vertices...");
		long t1 = System.currentTimeMillis();

		HashMap<Integer, GraphNode> vertices = DataReader.loadVertices(
				vertexFile, Share.initHashMapSize);
		long t2 = System.currentTimeMillis();
		System.out.println("Load vertices(s): " + (t2 - t1) / 1000.0);

		System.out.println("loading edges...");

		HashMap<Integer, GraphEdge> edges = DataReader.loadEdges(vertices,
				edgeFile, AUG, Share.initHashMapSize);

		long t3 = System.currentTimeMillis();

		System.out.println("Load edges(s): " + (t3 - t2) / 1000.0);

		Graph<GraphNode, GraphEdge> graph = GraphFactory
				.createDirectedSparseMultigraph(vertices, edges);

		long t4 = System.currentTimeMillis();
		System.out.println("creat graph (s): " + (t4 - t3) / 1000.0);

		// loading in-memory RTree
		// ISpatialIndex edgeRTree = RTreeLoadEdges(edgeTreeFile, 32, edges);

		// loading facilities
		// embed facilities to edges
		// so that facility and edge has has info
		System.out.println("loading facilities...");
		Map<Integer, Facility> facilities = DataReader.loadFacilities(
				facilityFile, edges, numFacilitiesToRead);

		// System.out.println("after augment: ");
		// printVertices();
		// printRoutes();

		// System.out.println("After augment, graph is " + graph.toString());
		// System.out.println("num nodes: " + graph.getVertexCount());
		// System.out.println("number of edges: " + graph.getEdgeCount());

		// loading routes
		System.out.println("loading routes...");
		HashMap<Integer, Route> routes = DataReader.loadRoutes(routesFile,
				edges, numRoutesToRead);

		long le = System.currentTimeMillis();
		System.out.println("load route(s) : " + (le - t4) / 1000.0);
		stats.loadDataTime = (le - ls) / 1000.0;

		System.out.println("Loading time: " + stats.loadDataTime);

		// 1. embed routes so that graph nodes (vertices and facilities)
		// know about the routes covering them
		// 2. routes know the number covered facilities.
		embedRoutes(graph, routes, edges, facilities);

		// add into stats the highest, lowest and avg score of routes
		// add into stats the highest, lowest and avg number of facilities
		Set<Integer> keys = routes.keySet();
		double max_s = Double.MIN_VALUE;
		int maxRouteid = -1;
		double min_s = Double.MAX_VALUE;
		double sum_s = 0;
		int max_f = Integer.MIN_VALUE;
		int min_f = Integer.MAX_VALUE;
		double sum_f = 0;
		for (Integer key : keys) {
			Route route = routes.get(key);
			if (route.getScore() > max_s) {
				max_s = route.getScore();
				maxRouteid = route.getId();
			}
			if (route.getScore() < min_s)
				min_s = route.getScore();
			if (route.getNumAttractedFacilities() > max_f)
				max_f = route.getNumAttractedFacilities();
			if (route.getNumAttractedFacilities() < min_f)
				min_f = route.getNumAttractedFacilities();
			sum_s += route.getScore();
			sum_f += route.getNumAttractedFacilities();
		}

		System.out.println("max route score id,  score, numberFac: "
				+ maxRouteid + ", " + max_s + ", "
				+ routes.get(maxRouteid).getNumAttractedFacilities());

		System.out.println();

		stats.maxRouteScore = max_s;
		stats.minRouteScore = min_s;
		stats.minNumFacility = min_f;
		stats.maxNumFacility = max_f;
		stats.numRoutes = routes.size();
		stats.avgRouteScore = sum_s / routes.size();
		stats.numFacilities = facilities.size();
		stats.avgNumFacility = sum_f / facilities.size();

		List<NetworkPoint> routeElocs = getRoutesAugELocations(routes);

		// augment facilities, start and end nodes to road network
		long taugs = System.currentTimeMillis();
		System.out.println("Augmenting graph...");
		augmentGraph(graph, facilities, routeElocs, vertices, edges, routes);
		long tauge = System.currentTimeMillis();
		System.out.println("Augmenting time(s)" + (tauge - taugs) / 1000.0);

		List<GraphEdge> result = scoreGraphEdges(graph, routes);

		stats.optimalScore = result.get(0).getScore();

		return result;
	}

	/**
	 * 
	 * @param routes
	 * @return list of first and last elocations of all routes
	 */
	private List<NetworkPoint> getRoutesAugELocations(
			HashMap<Integer, Route> routes) {
		List<NetworkPoint> elocs = new ArrayList<NetworkPoint>();
		for (Integer key : routes.keySet()) {
			Route route = routes.get(key);
			int len = route.getRoutePoints().length;
			elocs.add(route.getRoutePoints()[0]);
			elocs.add(route.getRoutePoints()[len - 1]);
		}
		return elocs;
	}

	/**
	 * The interactive method to find the edges with highest scores<br>
	 * the fundermantal difference is that<br>
	 * In this algorithm, the scores are not precomputed.<br>
	 * They are computed on the fly when needed.
	 * 
	 * @return
	 * @throws Exception
	 */
	List<SplitableSegment> findOptSegsIterative() throws Exception {
		long ls = System.currentTimeMillis();

		System.out.println("loading vertices...");
		HashMap<Integer, GraphNode> vertices = DataReader.loadVertices(
				vertexFile, Share.initHashMapSize);
		System.out.println("loading edges...");
		HashMap<Integer, GraphEdge> edges = DataReader.loadEdges(vertices,
				edgeFile, ITERATIVE, Share.initHashMapSize);
		Graph<GraphNode, GraphEdge> graph = GraphFactory
				.createDirectedSparseMultigraph(vertices, edges);

		// loading in-memory RTree
		// ISpatialIndex edgeRTree = RTreeLoadEdges(edgeTreeFile, 32, edges);

		// read facilities
		System.out.println("loading facilities...");
		Map<Integer, Facility> facilities = DataReader.loadFacilities(
				facilityFile, edges, numFacilitiesToRead);
		// read routes
		System.out.println("loading routes...");
		HashMap<Integer, Route> routes = DataReader.loadRoutes(routesFile,
				edges, numRoutesToRead);
		long le = System.currentTimeMillis();

		ITEPreProcess(graph, routes, edges, facilities);

		Set<Integer> keys = routes.keySet();
		int sumSampledNodes = 0;
		double max_s = Double.MIN_VALUE;
		double min_s = Double.MAX_VALUE;
		double sum_s = 0;
		int max_f = Integer.MIN_VALUE;
		int min_f = Integer.MAX_VALUE;
		double sum_f = 0;
		for (Integer key : keys) {
			Route route = routes.get(key);
			sumSampledNodes += route.getRoutePoints().length;
			if (route.getScore() > max_s) {
				max_s = route.getScore();
			}
			if (route.getScore() < min_s)
				min_s = route.getScore();
			if (route.getNumAttractedFacilities() > max_f)
				max_f = route.getNumAttractedFacilities();
			if (route.getNumAttractedFacilities() < min_f)
				min_f = route.getNumAttractedFacilities();
			sum_s += route.getScore();
			sum_f += route.getNumAttractedFacilities();
		}

		stats.maxRouteScore = max_s;
		stats.minRouteScore = min_s;
		stats.minNumFacility = min_f;
		stats.maxNumFacility = max_f;
		stats.numRoutes = routes.size();
		stats.avgRouteScore = sum_s / routes.size();
		stats.numFacilities = facilities.size();
		stats.avgNumFacility = sum_f / facilities.size();
		stats.loadDataTime = (le - ls) / 1000.0;
		stats.avgRouteNodes = sumSampledNodes / stats.numRoutes;

		// load routes into R-tree
		// ISpatialIndex routeRTree = RTreeLoadRoutes(routeTreeFile, 32,
		// routes);

		// embed facilities to edges
		// so that facility and edge has
		// has info
		// embedFacilities(facilities, edges, edgeRTree);
		// augmentGraph(graph, facilities, null, vertices, edges);

		// find out which facilities attract which routes
		// embedFacilitiesToRoutes(facilities, routes);

		// set score upper bounds and lower bounds for edges
		System.out.println("Setting upper and lower bounds...");
		List<SplitableSegment> splitableSegs = setScoreUBLBContainOverlapSets(
				routes, edges, graph);

		List<SplitableSegment> result = new ArrayList<SplitableSegment>();

		System.out.println("Adding segments to queue...");
		PriorityQueue<SplitableSegment> edgeQueueUB = loadEdgeToPQUB(splitableSegs);
		double maxLb = 0;

		System.out.println("Queue operations...");
		while (!edgeQueueUB.isEmpty()) {
			SplitableSegment currSeg = edgeQueueUB.poll();
			stats.totalNumSegs++;
			// System.out.println("curr maxLb: " + maxLb + "; curr seg: "
			// + currSeg.toString());

			boolean split = false;
			if (currSeg.getScoreUB() > maxLb) {
				split = true;
			} else if (currSeg.getScoreUB() == maxLb
					&& currSeg.getScoreUB() != 0) {
				if (currSeg.getScoreUB() == currSeg.getScoreLB()) {
					result.add(currSeg);
				} else {
					for (SplitableSegment s : result) {
						if (!s.getContainSet().containsAll(
								currSeg.getOverlapSet())) {
							split = true;
						} else {
							// prune2
							stats.prune2++;
						}
					}
				}
			} else {
				// currSeg.getScoreUB() <= maxLb
				// prune1
				stats.prune1++;
			}
			if (split) {
				stats.numSplits++;
				List<SplitableSegment> ss = splitSegmentHalf(currSeg, routes);

				// get containSet overlapSet, scoreUB and scoreLB for the segs
				calScoreUBLB(ss, routes, edges, graph);

				for (SplitableSegment s : ss) {
					// s's ub and lb is already computed at splitSegment
					if (s.getScoreLB() > maxLb) {
						maxLb = s.getScoreLB();
					}
					if (s.getScoreUB() != 0)
						edgeQueueUB.add(s);
				}
				// System.out.println("After spliting");
				// for (SplitableSegment s : ss) {
				// System.out.println(s.toString());
				// }
			}

		}
		stats.optimalScore = result.get(0).scoreUB;
		return result;
	}

	/**
	 * split given current segment into two equal smaller segments
	 * 
	 * @param seg
	 * @param routesMap
	 * 
	 * @return two smaller segments
	 */

	private List<SplitableSegment> splitSegmentHalf(SplitableSegment seg,
			HashMap<Integer, Route> routesMap) {
		List<SplitableSegment> res = new ArrayList<SplitableSegment>(2);
		double mid = (seg.getStartOnEdge() + seg.getEndOnEdge()) / 2;

		double[] midPoint = new double[2];
		midPoint[X] = (seg.getStartPoint()[X] + seg.getEndPoint()[X]) / 2;
		midPoint[Y] = (seg.getStartPoint()[Y] + seg.getEndPoint()[Y]) / 2;

		SplitableSegment seg1 = new SplitableSegment(seg.getNetEdgeId(),
				seg.getStartOnEdge(), mid, seg.getStartPoint(), midPoint);
		SplitableSegment seg2 = new SplitableSegment(seg.getNetEdgeId(), mid,
				mid, midPoint, midPoint);

		res.add(seg1);
		res.add(seg2);

		return res;
	}

	/**
	 * split given current segment into four equal smaller segments
	 * 
	 * @param seg
	 * @param routesMap
	 * 
	 * @return four smaller segments
	 */
	private List<SplitableSegment> splitSegmentQuad(SplitableSegment seg,
			HashMap<Integer, Route> routesMap) {
		int X = 0;
		int Y = 1;
		List<SplitableSegment> res = new ArrayList<SplitableSegment>(4);
		double mid = (seg.getStartOnEdge() + seg.getEndOnEdge()) / 2;
		double quad1 = (seg.getStartOnEdge() + mid) / 2;
		double quad3 = (seg.getEndOnEdge() + mid) / 2;

		double[] midPoint = new double[2];
		midPoint[X] = (seg.getStartPoint()[X] + seg.getEndPoint()[X]) / 2;
		midPoint[Y] = (seg.getStartPoint()[Y] + seg.getEndPoint()[Y]) / 2;

		double[] quadPoint = new double[2];
		quadPoint[X] = (seg.getStartPoint()[X] + midPoint[X]) / 2;
		quadPoint[Y] = (seg.getStartPoint()[Y] + midPoint[Y]) / 2;

		double[] thirdQuadPoint = new double[2];
		thirdQuadPoint[X] = (midPoint[X] + seg.getEndPoint()[X]) / 2;
		thirdQuadPoint[Y] = (midPoint[Y] + seg.getEndPoint()[Y]) / 2;

		SplitableSegment seg1 = new SplitableSegment(seg.getNetEdgeId(),
				seg.getStartOnEdge(), quad1, seg.getStartPoint(), quadPoint);
		SplitableSegment seg2 = new SplitableSegment(seg.getNetEdgeId(), quad1,
				mid, quadPoint, midPoint);

		SplitableSegment seg3 = new SplitableSegment(seg.getNetEdgeId(), mid,
				quad3, midPoint, thirdQuadPoint);
		SplitableSegment seg4 = new SplitableSegment(seg.getNetEdgeId(), quad3,
				seg.getEndOnEdge(), thirdQuadPoint, seg.getEndPoint());

		res.add(seg1);
		res.add(seg2);
		res.add(seg3);
		res.add(seg4);

		return res;
	}

	/**
	 * construct correct MBR from input segment<br>
	 * calculate scoreUB and scoreLB for one segment.
	 * 
	 * @param segment
	 * @param routeRTree
	 * @param routesMap
	 */
	void calScoreUBLBRTree(SplitableSegment segment, ISpatialIndex routeRTree,
			Map<Integer, Route> routesMap, Map<Integer, GraphEdge> edgesMap) {
		double[][] box = segment.getBoundingBox();
		RTreeUtil rtreeUtil = new RTreeUtil();

		List<Integer> routeIds = rtreeUtil.RTreeQuery(routeRTree,
				"intersection", box[0], box[1]);

		// System.out.println("seg" + segment.getSegId()
		// + " intersected with routes=" + routeIds);

		Set<Integer> overlapRids = new HashSet<Integer>(routeIds);
		Set<Integer> containRids = new HashSet<Integer>(overlapRids.size());
		// ss set overlapSet
		// ss updates the scoreUB
		segment.setOverlapSet(overlapRids);
		double sumUB = 0;
		double sumLB = 0;

		for (Integer i : overlapRids) {
			Route r = routesMap.get(i);
			sumUB += r.getScore() / (r.getNumAttractedFacilities() + 1);

			if (contains(r, segment, edgesMap)) {
				containRids.add(i);
				sumLB += r.getScore() / (r.getNumAttractedFacilities() + 1);
			}
		}
		segment.setContainSet(containRids);
		segment.setScoreUB(sumUB);
		segment.setScoreLB(sumLB);
	}

	/**
	 * Caution: rely on the routeId recording of vertices of the segment's edge
	 * 
	 * @param r
	 * @param segment
	 * @return true if r contains the segment
	 */
	private boolean contains(Route r, SplitableSegment segment,
			Map<Integer, GraphEdge> edgesMap) {

		GraphEdge currEdge = edgesMap.get(segment.sNode.getEdgeId());
		GraphNode src = currEdge.getSrcNode();
		GraphNode dest = currEdge.getSrcNode();
		// case 1: route totally cover the edge
		if (src.getRouteIds().contains(r.getId())
				&& dest.getRouteIds().contains(r.getId()))
			return true;

		// case 2: route does not intersect with the edge
		if (!src.getRouteIds().contains(r.getId())
				&& !dest.getRouteIds().contains(r.getId()))
			return false;

		// case 3: route intersects with the edge, but not contain
		if (src.getRouteIds().contains(r.getId())) {
			if (r.getRoutePoint(0).getEdgeId() == currEdge.getId()) {
				if (segment.eNode.getRatioFromNode() <= r.getRoutePoint(0)
						.getRatioFromNode())
					return true;
			} else if (r.getRoutePoint(r.getRoutePoints().length - 1)
					.getEdgeId() == currEdge.getId()) {

				if (segment.eNode.getRatioFromNode() <= r.getRoutePoint(
						r.getRoutePoints().length - 1).getRatioFromNode())
					return true;

			}
		} else if (dest.getRouteIds().contains(r.getId())) {
			if (r.getRoutePoint(0).getEdgeId() == currEdge.getId()) {
				if (segment.sNode.getRatioFromNode() > r.getRoutePoint(0)
						.getRatioFromNode())
					return true;
			} else if (r.getRoutePoint(r.getRoutePoints().length - 1)
					.getEdgeId() == currEdge.getId()) {
				if (segment.sNode.getRatioFromNode() >= r.getRoutePoint(
						r.getRoutePoints().length - 1).getRatioFromNode())
					return true;
			}
		}

		return false;

	}

	/**
	 * calculate scoreUB and scoreLB for one segment<br>
	 * set each ss's scoreUB and scoreLB
	 * 
	 * @param segmentList
	 * @param routeRTree
	 * @param routesMap
	 */
	private void calScoreUBLB(List<SplitableSegment> segmentList,
			Map<Integer, Route> routesMap, Map<Integer, GraphEdge> edgesMap,
			Graph graph) {
		for (SplitableSegment ss : segmentList) {
			Set<Integer> containSet = new HashSet<Integer>();
			Set<Integer> overlapSet = new HashSet<Integer>();
			fillContainOverlapSet(ss, routesMap, edgesMap, graph, containSet,
					overlapSet);

			// calculate the scoreUBLB of each ss
			double sumUB = 0;
			double sumLB = 0;

			for (Integer i : overlapSet) {
				Route r = routesMap.get(i);
				sumUB += r.getScore() / (r.getNumAttractedFacilities() + 1);
			}
			for (Integer i : containSet) {
				Route r = routesMap.get(i);
				sumLB += r.getScore() / (r.getNumAttractedFacilities() + 1);
			}
			ss.setScoreUB(sumUB);
			ss.setScoreLB(sumLB);
		}
	}

	/**
	 * 1. set UB, LB <br>
	 * 2. set contain set <br>
	 * 3. set overlap set<br>
	 * 
	 * @param routesMap
	 * @param edgesMap
	 * @return list of splitable segments
	 */
	List<SplitableSegment> setScoreUBLBContainOverlapSets(
			HashMap<Integer, Route> routesMap,
			HashMap<Integer, GraphEdge> edgesMap, Graph graph) {

		Set<Integer> keys = routesMap.keySet();
		Set<Integer> affectedEdges = new HashSet<Integer>();
		for (Integer key : keys) {
			Route r = routesMap.get(key);
			NetworkPoint[] routeNodes = r.getRoutePoints();

			List<Integer> eids = new ArrayList<Integer>();
			for (NetworkPoint rn : routeNodes) {
				if (!eids.contains(rn.getEdgeId()))
					eids.add(rn.getEdgeId());
				affectedEdges.add(rn.getEdgeId());
			}

			int numDistinctEdges = eids.size();

			// System.out.println("Total number changed eids in smoothening: "
			// + numChanged);
			// System.out
			// .println("In setScoreUBLBContainOverlapSets," + "route "
			// + key + ", total number distinct eids: "
			// + numDistinctEdges);

			double s = r.getScore() / (r.getNumAttractedFacilities() + 1);

			if (numDistinctEdges < 3) {

				// only intersection
				if (eids.size() == 1)
					((NetEdgeUB) edgesMap.get(routeNodes[0].getEdgeId()))
							.addScoreUB(s);
				else if (eids.size() > 1) {
					((NetEdgeUB) edgesMap.get(eids.get(0))).addScoreUB(s);
					((NetEdgeUB) edgesMap.get(eids.get(1))).addScoreUB(s);
				}

			} else {

				// intersection at two ends
				// containment in the middle
				int eid1 = eids.get(eids.size() - 1);
				NetEdgeUB firstEdge = (NetEdgeUB) edgesMap.get(eids.get(0));
				NetEdgeUB lastEdge = (NetEdgeUB) edgesMap.get(eid1);
				firstEdge.addScoreUB(s);
				lastEdge.addScoreUB(s);

				for (Integer i : eids) {
					if (i != eids.get(0) && i != eid1) {
						((NetEdgeUB) edgesMap.get(i)).addScoreLB(s);
						((NetEdgeUB) edgesMap.get(i)).addScoreUB(s);
					}
				}
			}
		}
		List<SplitableSegment> res = new ArrayList<SplitableSegment>(
				affectedEdges.size());
		// copy network edges to res
		for (Integer eid : affectedEdges) {
			NetEdgeUB e = (NetEdgeUB) edgesMap.get(eid);
			SplitableSegment ss = new SplitableSegment(e);
			// System.out.println("new split node: " + ss.toString());
			// set contain set and overlap set here
			Set<Integer> containSet = new HashSet<Integer>();
			Set<Integer> overlapSet = new HashSet<Integer>();
			fillContainOverlapSet(ss, routesMap, edgesMap, graph, containSet,
					overlapSet);
			// System.out.println("After filling contain and overlap set...");
			// System.out.println("contain:"+ss.getContainSet());
			// System.out.println("overlap: "+ss.getOverlapSet());
			// System.out.println();
			res.add(ss);
		}
		return res;
	}

	// /**
	// * 1. set UB, LB <br>
	// * 2. set contain set <br>
	// * 3. set overlap set<br>
	// *
	// * @param routesMap
	// * @param edgesMap
	// * @return list of splitable segments
	// */
	// List<SplitableSegment> setScoreUBLBContainOverlapSetsRTree(
	// HashMap<Integer, Route> routesMap,
	// HashMap<Integer, GraphEdge> edgesMap, ISpatialIndex routesRTree) {
	// Set<Integer> keys = routesMap.keySet();
	// for (Integer key : keys) {
	// Route r = routesMap.get(key);
	// NetworkPoint[] routeNodes = r.getRoutePoints();
	// int[] eids = new int[routeNodes.length];
	// for (int i = 0; i < eids.length; i++) {
	// eids[i] = routeNodes[i].getEdgeId();
	// }
	//
	// int numChanged = 0;
	// int numDistinctEdges = 1;
	// for (int i = 0; i < eids.length - 2; i++) {
	// if (eids[i] == eids[i + 2]) {
	// if (eids[i + 1] != eids[i]) {
	// eids[i + 1] = eids[i];
	// numChanged++;
	// }
	//
	// }
	// if (eids[i] != eids[i + 1]) {
	// numDistinctEdges++;
	// }
	// }
	// if (eids[eids.length - 2] != eids[eids.length - 1]) {
	// numDistinctEdges++;
	// }
	// // System.out.println("Total number changed eids in smoothening: "
	// // + numChanged);
	// // System.out.println("Total number distinct eids: "
	// // + numDistinctEdges);
	//
	// double s = r.getScore() / (r.getNumAttractedFacilities() + 1);
	//
	// if (numDistinctEdges < 3) {
	//
	// // only intersection
	// if (eids.length == 1)
	// ((NetEdgeUB) edgesMap.get(eids[0])).addScoreUB(s);
	// else if (eids.length > 1) {
	// ((NetEdgeUB) edgesMap.get(eids[0])).addScoreUB(s);
	// ((NetEdgeUB) edgesMap.get(eids[eids.length - 1]))
	// .addScoreUB(s);
	// }
	//
	// } else {
	//
	// // intersection at two ends
	// // containment in the middle
	// int eid1 = eids[eids.length - 1];
	// NetEdgeUB firstEdge = (NetEdgeUB) edgesMap.get(eids[0]);
	// NetEdgeUB lastEdge = (NetEdgeUB) edgesMap.get(eid1);
	// firstEdge.addScoreUB(s);
	// lastEdge.addScoreUB(s);
	//
	// Set<Integer> eidsMiddle = new HashSet<Integer>();
	// for (Integer i : eids) {
	// if (i != eids[0] && i != eid1) {
	// eidsMiddle.add(i);
	// }
	// }
	// for (Integer i : eidsMiddle) {
	// ((NetEdgeUB) edgesMap.get(i)).addScoreLB(s);
	// ((NetEdgeUB) edgesMap.get(i)).addScoreUB(s);
	// }
	// }
	// }
	//
	// List<SplitableSegment> res = new ArrayList<SplitableSegment>(
	// edgesMap.size());
	// // copy network edges to res
	// Set<Integer> eids = edgesMap.keySet();
	// for (Integer eid : eids) {
	// NetEdgeUB e = (NetEdgeUB) edgesMap.get(eid);
	// SplitableSegment ss = new SplitableSegment(e);
	// // System.out.println("new split node: " + ss.toString());
	// // set contain set and overlap set here
	// Set<Integer> containSet = new HashSet<Integer>();
	// Set<Integer> overlapSet = new HashSet<Integer>();
	// fillContainOverlapSetRTree(ss, routesMap, routesRTree, containSet,
	// overlapSet);
	// // System.out.println("After filling contain and overlap set...");
	// // System.out.println("contain:"+ss.getContainSet());
	// // System.out.println("overlap: "+ss.getOverlapSet());
	// // System.out.println();
	// res.add(ss);
	// }
	// return res;
	// }

	/**
	 * fill up two sets and set ss's contain and overlap sets
	 * 
	 * @param ss
	 * @param routesMap
	 * @param containSet
	 * @param overlapSet
	 */
	private void fillContainOverlapSet(SplitableSegment ss,
			Map<Integer, Route> routesMap, Map<Integer, GraphEdge> edgesMap,
			Graph graph, Set<Integer> containSet, Set<Integer> overlapSet) {
		NetworkPoint sNode = ss.getsNode();
		NetworkPoint eNode = ss.geteNode();

		GraphEdge theEdge = edgesMap.get(ss.getNetEdgeId());
		Set<Integer> coveringRids = theEdge.getRouteIds();

		for (int key : coveringRids) {
			Route r = routesMap.get(key);
			NetworkPoint[] elocs_r = r.getRoutePoints();
			boolean b1 = covers(elocs_r, sNode, delta, edgesMap, graph);
			boolean b2 = covers(elocs_r, eNode, delta, edgesMap, graph);
			if (b1 && b2) {
				containSet.add(key);
			}
			if (b1 || b2) {
				overlapSet.add(key);
			}

		}

		ss.setContainSet(containSet);
		ss.setOverlapSet(overlapSet);
	}

	/**
	 * 1. assign scores to edges <br>
	 * 2. load scored edges to PQ
	 * 
	 * @param graph
	 * @return all edges with highest scores
	 */
	List<GraphEdge> scoreGraphEdges(Graph<GraphNode, GraphEdge> graph,
			HashMap<Integer, Route> routes) {
		List<GraphEdge> resEdges = new ArrayList<GraphEdge>();
		double maxScoreSoFar = Double.MIN_VALUE;

		Collection<GraphEdge> edges = graph.getEdges();
		for (GraphEdge e : edges) {
			GraphNode src = (GraphNode) e.getSrcNode();
			GraphNode dest = (GraphNode) e.getDestNode();
			if (src.equals(dest)) {
				continue;
			}
			Set<Integer> srcList = src.getRouteIds();
			Set<Integer> destList = dest.getRouteIds();
			if (srcList != null && destList != null && srcList.size() != 0
					&& destList.size() != 0) {
				Collection<Integer> common = CollectionUtils.intersection(
						srcList, destList);
				double score = 0;
				for (Integer routeId : common) {
					Route r = routes.get(routeId);
					score += r.getScore() / (r.getNumAttractedFacilities() + 1);
				}
				e.setScore(score);
				if (score > maxScoreSoFar) {
					// throw away existing results
					// keep results with same score
					resEdges.clear();
					resEdges.add(e);
					maxScoreSoFar = score;
				} else if (score == maxScoreSoFar) {
					resEdges.add(e);
				}
				// throw away e if e has lower score
			}
		}
		return resEdges;
	}

	/**
	 * In this priority queue, edges are ordered by score upper bound
	 * 
	 * @param splitableSegs
	 * 
	 * @param graph
	 * @return the priority queue with all edges
	 */
	PriorityQueue<SplitableSegment> loadEdgeToPQUB(
			List<SplitableSegment> splitableSegs) {
		PriorityQueue<SplitableSegment> pQueue = new PriorityQueue<SplitableSegment>();
		for (SplitableSegment seg : splitableSegs) {
			if (seg.getScoreUB() != 0) {
				pQueue.add(seg);
			}
		}
		return pQueue;
	}

	/**
	 * ITE PreProcess<br>
	 * 1. embed routes so that ELocations and facilities know about the routes
	 * covering them <br>
	 * 2. routes know the number attracting facilities.<br>
	 * 3. update the coveredRid fields for each edge <br>
	 * 
	 */
	void ITEPreProcess(Graph graph, HashMap<Integer, Route> routes,
			HashMap<Integer, GraphEdge> edgesMap, Map<Integer, Facility> fMap) {
		for (Integer key : routes.keySet()) {
			Route route = routes.get(key);
			List<GraphEdge> coveredEdges = findCoveredEdgesForRoute(route,
					edgesMap);

			// register routeid to the end vertices of the covered edges
			// first edge and last edge are interesections
			// in-between edges are contained
			GraphEdge edge1 = edgesMap.get(route.getRoutePoint(0).getEdgeId());
			int index = 1;
			GraphEdge edgeNext = edgesMap.get(route.getRoutePoint(index)
					.getEdgeId());

			while (edgeNext.equals(edge1)) {
				edgeNext = edgesMap.get(route.getRoutePoint(++index)
						.getEdgeId());
			}
			GraphNode node1 = getConnection(graph, edge1, edgeNext);
			node1.addRid(route.getId());

			GraphEdge edge2 = edgesMap.get(route.getRoutePoint(
					route.getRoutePoints().length - 1).getEdgeId());
			index = route.getRoutePoints().length - 2;
			edgeNext = edgesMap.get(route.getRoutePoint(index).getEdgeId());
			while (edgeNext.equals(edge1)) {
				edgeNext = edgesMap.get(route.getRoutePoint(--index)
						.getEdgeId());
			}
			node1 = getConnection(graph, edge2, edgeNext);
			node1.addRid(route.getId());

			for (GraphEdge ge : coveredEdges) {
				if (ge.getId() != edge1.getId() && ge.getId() != edge2.getId()) {
					ge.getSrcNode().addRid(route.getId());
					ge.getDestNode().addRid(route.getId());
				}
			}

			//do for facilities
			Set<Integer> fs = findCoveredFacilitiesForRoute(route,
					coveredEdges, edgesMap, fMap, graph);

			for (Integer i : fs) {
				Facility f = fMap.get(i);
				f.addRid(route.getId());
			}

			// System.out.println("route" + route.getId()
			// + " covered facilities:" + fs);

			route.setNumAttractedFacilities(fs.size());

			coveredEdges.clear();
			fs.clear();
		}
	}

	/**
	 * AUG <br>
	 * 
	 * 1. embed routes so that ELocations and facilities know about the routes
	 * covering them <br>
	 * 2. routes know the number covered facilities.<br>
	 * 3. update the coveredRid fields for each edge <br>
	 * 4. update connection points' covering routes field <br>
	 * 
	 * 
	 * 
	 * 
	 * @param routes
	 * @param edges
	 * @param facilities
	 */
	private void embedRoutes(Graph graph, HashMap<Integer, Route> routes,
			HashMap<Integer, GraphEdge> edgesMap, Map<Integer, Facility> fMap) {

		for (Integer key : routes.keySet()) {
			Route route = routes.get(key);
			List<GraphEdge> coveredEdges = findCoveredEdgesForRoute(route,
					edgesMap);

			Set<Integer> fs = findCoveredFacilitiesForRoute(route,
					coveredEdges, edgesMap, fMap, graph);

			for (Integer i : fs) {
				Facility f = fMap.get(i);
				f.addRid(route.getId());
			}
			//
			// System.out.println("route" + route.getId()
			// + " covered facilities:" + fs);

			route.setNumAttractedFacilities(fs.size());

			// update the routeId list for each connection
			// original graph nodes are filled up with rids here
			GraphNode firstNodeSrc = coveredEdges.get(0).getSrcNode();
			GraphNode lastNodeSrc = coveredEdges.get(coveredEdges.size() - 1)
					.getSrcNode();

			NetworkPoint firstEloc = route.getRoutePoint(0);
			int len = route.getRoutePoints().length;
			NetworkPoint lastEloc = route.getRoutePoints()[len - 1];
			if (firstEloc.getRatioFromNode() <= delta) {
				firstNodeSrc.addRid(route.getId());
			}
			if (lastEloc.getRatioFromNode() <= delta) {
				lastNodeSrc.addRid(route.getId());
			}

			Iterator<GraphEdge> ite = coveredEdges.iterator();
			GraphEdge lEdge = null;
			while (ite.hasNext()) {
				GraphEdge anEdge;
				if (lEdge != null) {
					anEdge = lEdge;
				} else {
					anEdge = ite.next();
				}

				// find connection between any two edges
				if (ite.hasNext()) {
					GraphEdge edge2 = ite.next();
					GraphNode connNode = getConnection(graph, anEdge, edge2);
					if (connNode != null)
						connNode.addRid(route.getId());
					lEdge = edge2;
				}
			}
		}
	}

	/**
	 * 
	 * @param route
	 * @param coveredEdges
	 * @param edgesMap
	 * @return list of facilities that attract the route
	 */
	private Set<Integer> findCoveredFacilitiesForRoute(Route route,
			List<GraphEdge> coveredEdges, HashMap<Integer, GraphEdge> edgesMap,
			Map<Integer, Facility> fMap, Graph graph) {

		Set<Integer> res = new HashSet<Integer>();
		for (GraphEdge e : coveredEdges) {
			List<Integer> fids = e.getFids();
			for (Integer fid : fids) {
				Facility f = fMap.get(fid);
				if (covers(route.getRoutePoints(), f.getEloc(), delta,
						edgesMap, graph)) {
					res.add(f.getId());
				}
			}
		}

		return res;
	}

	/**
	 * 
	 * @param route
	 * @param edges
	 * @return list of distinct covered edges
	 */
	private List<GraphEdge> findCoveredEdgesForRoute(Route route,
			HashMap<Integer, GraphEdge> edgesMap) {
		Set<Integer> eids = new HashSet<Integer>();

		for (NetworkPoint eloc : route.getRoutePoints()) {
			eids.add(eloc.getEdgeId());
		}
		List<GraphEdge> res = new ArrayList<GraphEdge>();
		for (Integer i : eids) {
			res.add(edgesMap.get(i));
		}
		return res;
	}

	/**
	 * 
	 * @param edge1
	 * @param edge2
	 * @return the connection between edge1 and edge2
	 */
	GraphNode getConnection(Graph graph, GraphEdge edge1, GraphEdge edge2) {
		GraphNode n1src = (GraphNode) graph.getSource(edge1);
		GraphNode n1dest = (GraphNode) graph.getDest(edge1);

		GraphNode n2src = (GraphNode) graph.getSource(edge2);
		GraphNode n2dest = (GraphNode) graph.getDest(edge2);

		if (n1src.equals(n2src) || n1src.equals(n2dest)) {
			return n1src;
		} else if (n1dest.equals(n2dest) || n1dest.equals(n2src)) {
			return n1dest;
		}
		return null;
	}

	/**
	 * Model 1 is equal distribution of score <br>
	 * 1. get to know attracted facilities and netNodes <br>
	 * 2. get the list of edgeIds covered by the route <br>
	 * 3. for first and last edges, get the attracted facilities <br>
	 * 4. get all facilities for middle edges <br>
	 * 5. create new edges and compute scores for them
	 * 
	 * @param r
	 */
	// private void distributeScoreModel1(Route r) {
	// List<Facility> coveredFacilities = findCoveredFacilitiesForRoute(r);
	//
	// // Augment graph only if facilities are covered by routes
	// if (coveredFacilities.size() != 0) {
	// augmentGraphNodes(r, coveredEdges, coveredFacilities);
	// }
	// // allocate score
	// double score = r.getScore();
	// double portion = score / (coveredFacilities.size() + 1);
	// int length = r.getRouteNodes().length;
	// RouteNode rns = r.getRouteNodes()[0];
	// RouteNode rne = r.getRouteNodes()[length - 1];
	// DijkstraShortestPath<GraphNode, GraphEdge> dij = new
	// DijkstraShortestPath<>(
	// graph);
	//
	// // case 1: one facility
	// // case 2: two facilities
	// // case 3: more than two
	// if (coveredFacilities.size() == 1) {
	// List<GraphEdge> li = dij.getPath(rns, coveredFacilities.get(0));
	// for (GraphEdge ge : li) {
	// ge.setScore(portion);
	// }
	// } else if (coveredFacilities.size() == 2) {
	// List<GraphEdge> li = dij.getPath(rns, coveredFacilities.get(0));
	// for (GraphEdge ge : li) {
	// ge.setScore(portion);
	// }
	// li = dij.getPath(coveredFacilities.get(1), rne);
	// for (GraphEdge ge : li) {
	// ge.setScore(portion);
	// }
	// } else {
	// List<GraphEdge> li = dij.getPath(rns, coveredFacilities.get(0));
	// int size = coveredFacilities.size();
	// for (GraphEdge ge : li) {
	// ge.setScore(portion);
	// }
	// li = dij.getPath(coveredFacilities.get(size - 1), rne);
	// for (GraphEdge ge : li) {
	// ge.setScore(portion);
	// }
	//
	// Iterator<Facility> ite = coveredFacilities.iterator();
	// while (ite.hasNext()) {
	// Facility f1 = ite.next();
	// if (ite.hasNext()) {
	// Facility f2 = ite.next();
	// li = dij.getPath(f1, f2);
	// for (GraphEdge ge : li) {
	// ge.setScore(portion);
	// }
	// }
	// }
	// }
	// }

	// private void augmentFacilities(List<Facility> facilities) throws
	// Exception {
	// for (Facility f : facilities) {
	// if (f.getEdgeId() == -1) {
	// throw new NotMapMatchedException(f.toString());
	// }
	// augmentGraphNode(f);
	// }
	// }

	/**
	 * Main method to mutate the graph <br>
	 * update edges and vertices
	 * 
	 * @param graph
	 * @param facilities
	 * @param endPoints
	 * @param veticesMap
	 * @param edges
	 * @throws Exception
	 */
	private void augmentGraph(Graph graph, Map<Integer, Facility> fs,
			List<NetworkPoint> endPoints, Map<Integer, GraphNode> verticesMap,
			Map<Integer, GraphEdge> edges, Map<Integer, Route> routesMap)
			throws Exception {
		// Step 1. get affected edges
		// go by edge
		Set<Integer> eidSet = new HashSet<Integer>();
		// only edges that are covered by routes need to be augmented
		if (endPoints != null) {
			for (NetworkPoint p : endPoints) {
				eidSet.add(p.getEdgeId());
			}
		}
		for (Integer eid : eidSet) {
			List<NetworkPoint> elocs = new ArrayList<NetworkPoint>();
			// add f's elocation into elocs
			for (Integer fi : fs.keySet()) {
				Facility f = fs.get(fi);
				if (f.getEdgeId() == eid) {
					elocs.add(f.getEloc());
				}
			}
			// add each end point into elocs
			if (endPoints != null) {
				for (NetworkPoint p : endPoints) {
					if (p.getEdgeId() == eid) {
						elocs.add(p);
					}
				}
			}
			// sort nodes according to their ratioFromNodes
			Collections.sort(elocs);
			// find out the covering routes for each eloc
			// facility and route endings are filled up with rids here
			Set<Integer> coveringRouteIds = ((NetEdge) edges.get(eid))
					.getRouteIds();
			for (Integer integ : coveringRouteIds) {
				Route r = routesMap.get(integ);
				NetworkPoint[] elocs_r = r.getRoutePoints();
				for (NetworkPoint eloc : elocs) {
					if (covers(elocs_r, eloc, delta, edges, graph)) {
						eloc.addRid(r.getId());
					}
				}
			}

			GraphEdge tempE = edges.get(eid);
			GraphNode tempDest = tempE.getDestNode();
			// System.out.println("eid: " + eid + ", dest rids: "
			// + tempDest.getRouteIds());
			// System.out.println("eid " + eid + ", elocs: " + elocs);

			// graph add sequentially
			GraphEdge ne = edges.get(eid);
			GraphNode source = (GraphNode) graph.getSource(ne);
			GraphNode dest = (GraphNode) graph.getDest(ne);
			// add edges
			GraphNode lastNode = elocs.get(elocs.size() - 1);
			NetEdge edge1 = new NetEdge(Sequencer.next(), source, elocs.get(0));
			NetEdge edge2 = new NetEdge(Sequencer.next(), lastNode, dest);

			graph.addEdge(edge1, source, elocs.get(0));
			graph.addEdge(edge2, lastNode, dest);
			edges.put(edge1.getId(), edge1);
			edges.put(edge2.getId(), edge2);

			Iterator<NetworkPoint> ite = elocs.iterator();
			GraphNode lNode = null;
			while (ite.hasNext()) {
				GraphNode node;
				if (lNode != null) {
					node = lNode;
				} else {
					node = ite.next();
				}
				// update vertices
				verticesMap.put(node.getId(), node);

				// add an edge between any two vertices
				if (ite.hasNext()) {
					GraphNode node1 = ite.next();
					NetEdge e = new NetEdge(Sequencer.next(), node, node1);
					graph.addEdge(e, node, node1);
					edges.put(e.getId(), e);
					lNode = node1;
				}
			}

			// remove old edges
			// graph.removeEdge(ne);
			// edges.remove(ne.getId());
		}

	}

	private List<Facility> findCoveredFacilities(GraphEdge firstEdge,
			NetworkPoint startNode, NetworkPoint secondNode, double delta,
			Map<Integer, GraphEdge> edgesMap, Map<Integer, Facility> fMap) {
		List<Integer> fids = firstEdge.getFids();

		List<Facility> resfs = new ArrayList<Facility>();
		// NetworkPoint loc1 = startNode.getEloc();
		// NetworkPoint loc2 = secondNode.getEloc();

		for (Integer fid : fids) {
			Facility f = fMap.get(fid);
			NetworkPoint locTBD = f.getEloc();
			if (covers(startNode, secondNode, locTBD, delta)) {
				resfs.add(f);
			}
		}
		return resfs;
	}

	/**
	 * pre-condition: loc1, loc2 and locTBD are on the same edge
	 * 
	 * @param loc1
	 * @param loc2
	 * @param locTBD
	 * @return true if case1: f is covered by loc1 and loc2 within delta case2:
	 *         f is covered by elongation from loc1 to loc2
	 */
	public boolean covers(NetworkPoint loc1, NetworkPoint loc2,
			NetworkPoint locTBD, double delta) {

		double offsetmin = Math.min(loc1.getRatioFromNode(),
				loc2.getRatioFromNode());
		double offsetmax = Math.max(loc1.getRatioFromNode(),
				loc2.getRatioFromNode());

		if (locTBD.getRatioFromNode() <= (offsetmax + delta)
				&& locTBD.getRatioFromNode() >= (offsetmin - delta))
			return true;
		// else {
		// if (loc1.offsetFromNode < loc2.offsetFromNode) {
		// return locTBD.offsetFromNode > loc2.offsetFromNode;
		// } else {
		// return locTBD.offsetFromNode <= loc2.offsetFromNode;
		// }
		// }
		return false;
	}

	// /**
	// * augment original graph with either route nodes or facilities
	// *
	// * @param graphNode
	// */
	// void augmentGraphNode(GraphNode graphNode) {
	//
	// int edgeId = -1;
	// if (graphNode instanceof Facility)
	// edgeId = ((Facility) graphNode).getEdgeId();
	// else if (graphNode instanceof RouteNode) {
	// edgeId = ((RouteNode) graphNode).getEdgeId();
	// }
	// if (edgeId == -1) {
	// ELocation eloc = mapMatch(numTrials, graphNode);
	// edgeId = eloc.edgeId;
	// }
	// NetEdge origEdge = edges.get(edgeId);
	// // Pair<NetNode> pair = graph.getEndpoints(origEdge);
	// //
	// // NetNode srcNode = (NetNode) pair.getFirst();
	// // NetNode destNode = (NetNode) pair.getSecond();
	//
	// NetNode srcNode = (NetNode) graph.getSource(origEdge);
	// NetNode destNode = (NetNode) graph.getDest(origEdge);
	//
	// // add edges
	// NetEdge edge1 = new NetEdge(Sequencer.next(), srcNode, graphNode, null);
	// NetEdge edge2 = new NetEdge(Sequencer.next(), graphNode, destNode, null);
	//
	// graph.addEdge(edge1, srcNode, graphNode);
	// graph.addEdge(edge2, graphNode, destNode);
	//
	// // remove old edges
	// graph.removeEdge(origEdge);
	//
	//
	// }

	/**
	 * 
	 * @param route
	 * @param numTrials
	 * @return The list of Elocs which each of the route nodes is matched to
	 */
	public List<NetworkPoint> mapMatch(Route route, int numTrials,
			Map<Integer, GraphEdge> edgesMap, ISpatialIndex edgeRTree) {
		List<NetworkPoint> resLocs = new ArrayList<NetworkPoint>();
		for (NetworkPoint rnode : route.getRoutePoints()) {
			NetworkPoint eloc = mapMatch(numTrials, rnode, edgesMap, edgeRTree);
			resLocs.add(eloc);
		}
		return resLocs;
	}

	/**
	 * basic function for mapmatching a graph node to its expected location on
	 * an nearby edge
	 * 
	 */
	private NetworkPoint mapMatch(int numTrials, GraphNode gnode,
			Map<Integer, GraphEdge> edgesMap, ISpatialIndex RTree) {
		double[] point = { gnode.x, gnode.y };
		NetworkPoint eloc = getExpLocationOnNearestEdge(numTrials, point,
				edgesMap, RTree);
		return eloc;
	}

	// /**
	// *
	// * @param edgeFile
	// * @return the list of facilities from the file
	// */
	// private List<Facility> loadFacilities(String edgeFile) {
	// List<Facility> fs = new ArrayList<Facility>();
	// BufferedReader bufferedReader = null;
	// try {
	// bufferedReader = new BufferedReader(new FileReader(edgeFile));
	// String line = null;
	// StringTokenizer st = null;
	// while ((line = bufferedReader.readLine()) != null) {
	// if (line.startsWith("#")) {
	// continue;
	// }
	// st = new StringTokenizer(line);
	// // Process the data
	// int id = Integer.parseInt(st.nextToken());
	// double x = Double.parseDouble(st.nextToken());
	// double y = Double.parseDouble(st.nextToken());
	// int edgeId = Integer.parseInt(st.nextToken());
	// double ratioFromNode = Double.parseDouble(st.nextToken());
	// double distFromNode = Double.parseDouble(st.nextToken());
	//
	// fs.add(new Facility(id, x, y, edgeId, ratioFromNode,
	// distFromNode));
	// }
	//
	// bufferedReader.close();
	// } catch (Exception ex) {
	// ex.printStackTrace();
	// }
	//
	// return fs;
	// }

	/**
	 * 
	 * @param vertices
	 * @param edges
	 * @return
	 * @throws IOException
	 */
	public Graph<GraphNode, GraphEdge> createUndirectedSparsegraph(
			Map<Integer, GraphNode> vertices, Map<Integer, GraphEdge> edges)
			throws IOException {

		UndirectedSparseGraph<GraphNode, GraphEdge> graph = new UndirectedSparseGraph<GraphNode, GraphEdge>();
		Set<Integer> keys = vertices.keySet();
		for (Integer key : keys) {
			NetNode node = (NetNode) vertices.get(key);
			graph.addVertex(node);
		}

		// add edges
		Set<Integer> edgekeys = edges.keySet();
		for (int ei : edgekeys) {
			GraphEdge e = edges.get(ei);

			graph.addEdge(e, vertices.get(e.getSrcId()),
					vertices.get(e.getDestId()));
		}

		return graph;

	}

	/**
	 * determine if route covers facility
	 * 
	 * @param route
	 * @param facility
	 * @param delta
	 * @param numTrials
	 * @return true if the route and facility are within delta network distance
	 */
	public boolean attracts(Route route, Facility facility, double delta,
			int numTrials, Map<Integer, GraphEdge> edgesMap, Graph graph) {
		// 1. get the list of edges for the route by doing NN search on each
		// point of the route
		// 2. if Eloc of facility is in internal edge, then return true
		// 3. else if Eloc of facility is on first or last edge, <br>
		// if Eloc of facility and Eloc of first or last point of route near
		// each other
		// return true
		// else return false;
		NetworkPoint[] mapmatchedNodes = route.getRoutePoints();
		return covers(mapmatchedNodes, facility.getEloc(), delta, edgesMap,
				graph);
	}

	/**
	 * determine if an eloc is inbetween an array of elocs
	 * 
	 * @param elocs
	 * @param elocTBD
	 * @param delta
	 * @param edgesMap
	 * @param graph
	 * @return true if a sequence of elocs cover one gnode
	 */
	private boolean covers(NetworkPoint[] elocs, NetworkPoint elocTBD,
			double delta, Map<Integer, GraphEdge> edgesMap, Graph graph) {

		for (int i = 0; i < elocs.length - 1; i++) {
			// case 1; before
			if ((elocs[i].getEdgeId() == elocTBD.getEdgeId())
					&& elocs[i + 1].getEdgeId() != elocTBD.getEdgeId()) {
				// find the graph node connecting elocs[i].getEdgeId() and
				// elocs[i+1].getEdgeId()
				GraphEdge edge1 = edgesMap.get(elocs[i].getEdgeId());
				GraphEdge edge2 = edgesMap.get(elocs[i + 1].getEdgeId());

				GraphNode connNode = getConnection(graph, edge1, edge2);
				if (connNode != null) {
					// check connNode is src or dest
					if (connNode.equals(edge1.getDestNode())) {
						return elocs[i].getRatioFromNode() - delta <= elocTBD
								.getRatioFromNode();
					} else {
						// connNode is edge1's src node
						return elocs[i].getRatioFromNode() + delta >= elocTBD
								.getRatioFromNode();
					}
				}

			}
			// case 2: after
			if ((elocs[i].getEdgeId() != elocTBD.getEdgeId())
					&& elocs[i + 1].getEdgeId() == elocTBD.getEdgeId()) {
				GraphEdge edge1 = edgesMap.get(elocs[i].getEdgeId());
				GraphEdge edge2 = edgesMap.get(elocs[i + 1].getEdgeId());
				GraphNode connNode = getConnection(graph, edge1, edge2);

				if (connNode != null) {
					// check connNode is src or dest
					if (connNode.equals(edge2.getDestNode())) {
						return elocs[i + 1].getRatioFromNode() - delta <= elocTBD
								.getRatioFromNode();
					} else {
						// connNode is edge1's src node
						return elocs[i + 1].getRatioFromNode() + delta >= elocTBD
								.getRatioFromNode();
					}
				}
			}

			// case 3: in between
			if ((elocs[i].getEdgeId() == elocTBD.getEdgeId())
					&& elocs[i + 1].getEdgeId() == elocTBD.getEdgeId()
					&& (covers(elocs[i], elocs[i + 1], elocTBD, delta))) {
				return true;
			}
		}
		return false;
	}

	/**
	 * 
	 * @param node
	 * @param edge
	 * @return the expected location of the node on the edge
	 */
	private NetworkPoint getExpLocation(GraphNode node, GraphEdge edge) {

		Coordinate pFrom = new Coordinate(edge.getSrcNode().x,
				edge.getSrcNode().y);
		Coordinate pTo = new Coordinate(edge.getDestNode().x,
				edge.getDestNode().y);
		LineSegment ls = new LineSegment(pFrom, pTo);
		Coordinate p = new Coordinate(node.x, node.y);
		// double d1 = pFrom.distance(p);
		double ratio = ls.projectionFactor(p);
		// return new ELocation(Sequencer.next(), edge.getId(), ratio, d1);
		return new NetworkPoint(Sequencer.next(), edge.getId(), ratio);
	}

	/**
	 * 
	 * @param k
	 * @param point
	 * @param edges
	 * @edgeRTree
	 * @return a coordinate its expected location on network
	 */
	public NetworkPoint getExpLocationOnNearestEdge(int k, double[] point,
			Map<Integer, GraphEdge> edges, ISpatialIndex edgeRTree) {
		// 1. index edges with in-memory RTree as line segments <br>
		// 2. do NN search with the point -> netedge <br>
		// 3. return expected location on the netedge <br>

		RTreeUtil rTreeUtil = new RTreeUtil();
		List<Integer> resultsEdgeIds = rTreeUtil.RTreeQuery(edgeRTree,
				k + "NN", point, null);

		// find the edge with shortest distance
		// by scanning NN
		GraphEdge canEdge = null;
		double distSoFar = Double.MAX_VALUE;
		for (int eid : resultsEdgeIds) {
			GraphEdge edge = edges.get(eid);
			double dist = edge.computeDistanceTo(point);
			if (dist < distSoFar) {
				distSoFar = dist;
				canEdge = edge;
			}
		}
		if (canEdge == null) {
			return null;
		}
		// Coordinate pFrom = new Coordinate(canEdge.getSrcNode().x,
		// canEdge.getSrcNode().y);
		// Coordinate pTo = new Coordinate(canEdge.getDestNode().x,
		// canEdge.getDestNode().y);
		// LineSegment ls = new LineSegment(pFrom, pTo);
		// double d1 = ls.projectionFactor(new Coordinate(point[0], point[1]));
		// eloc = new ELocation(Sequencer.next(), canEdge.getId(), d1, (1 -
		// d1));

		GraphNode node = new GraphNode(Sequencer.next(), point[0], point[1]);
		return getExpLocation(node, canEdge);
	}

	// public static Graph genGraph() {
	// Graph g;
	// NetNode n1, n2, n3, n4, n5;
	// n1 = new NetNode(1);
	// n2 = new NetNode(2);
	// n3 = new NetNode(3);
	// n4 = new NetNode(4);
	// n5 = new NetNode(5); // note n1-n5 declared elsewhere.
	// List<NetNode> nodes = new ArrayList<NetNode>(5);
	// nodes.add(n1);
	// nodes.add(n2);
	// nodes.add(n3);
	// nodes.add(n4);
	// nodes.add(n5);
	// for (NetNode n : nodes) {
	// g.addVertex(n);
	// }
	//
	// NetEdge e1 = new NetEdge(0, 2.0);
	// NetEdge e2 = new NetEdge(1, 2.0);
	// NetEdge e3 = new NetEdge(2, 2.0);
	//
	// // Add some edges. From above we defined these to be of type String
	// // Note that the default is for undirected edges.
	// g.addEdge(e1, n1, n2); // Note that Java 1.5 auto-boxes primitives
	// g.addEdge(e2, n2, n3);
	//
	// System.out.println("The graph g = " + g.toString());
	//
	// return g;
	// }

	// /**
	// *
	// * @param routeTreeFile
	// * @param capacity
	// * @param routesMap
	// * @return routeRTree
	// */
	// private ISpatialIndex RTreeLoadRoutes(String routeTreeFile, int capacity,
	// HashMap<Integer, Route> routesMap) {
	// ISpatialIndex routeRTree = null;
	// try {
	//
	// // specify the page size. Since the index may also contain user
	// // defined data
	// // there is no way to know how big a single node may become. The
	// // storage manager
	// // will use multiple pages per node if needed. Off course this will
	// // slow down performance.
	//
	// IStorageManager diskfile = new MemoryStorageManager();
	// // IStorageManager diskfile = new DiskStorageManager(ps);
	//
	// IBuffer file = new RandomEvictionsBuffer(diskfile, 10, false);
	// // applies a main memory random buffer on top of the persistent
	// // storage manager
	// // (LRU buffer, etc can be created the same way).
	//
	// // Create a new, empty, RTree with dimensionality 2, minimum load
	// // 70%, using "file" as
	// // the StorageManager and the RSTAR splitting policy.
	// PropertySet ps2 = new PropertySet();
	//
	// Double f = new Double(0.7);
	// ps2.setProperty("FillFactor", f);
	//
	// ps2.setProperty("IndexCapacity", capacity);
	// ps2.setProperty("LeafCapacity", capacity);
	// // Index capacity and leaf capacity may be different.
	//
	// int dim = new Integer(2);
	// ps2.setProperty("Dimension", dim);
	//
	// routeRTree = new RTree(ps2, file);
	// int id;
	//
	// long start = System.currentTimeMillis();
	// // String line = lr.readLine();
	// Set<Integer> routekeys = routesMap.keySet();
	// for (int rid : routekeys) {
	// Route route = routesMap.get(rid);
	// id = route.getId();
	// double[] f1 = { route.getXmin(), route.getYmin() };
	// double[] f2 = { route.getXmax(), route.getYmax() };
	//
	// // insert
	// Region r = new Region(f1, f2);
	//
	// String data = r.toString();
	// // associate some data with this region. I will use a string
	// // that represents the
	// // region itself, as an example.
	// // NOTE: It is not necessary to associate any data here. A
	// // null pointer can be used. In that
	// // case you should store the data externally. The index will
	// // provide the data IDs of
	// // the answers to any query, which can be used to access the
	// // actual data from the external
	// // storage (e.g. a hash table or a database table, etc.).
	// // Storing the data in the index is convinient and in case a
	// // clustered storage manager is
	// // provided (one that stores any node in consecutive pages)
	// // performance will improve substantially,
	// // since disk accesses will be mostly sequential. On the
	// // other hand, the index will need to
	// // manipulate the data, resulting in larger overhead. If you
	// // use a main memory storage manager,
	// // storing the data externally is highly recommended
	// // (clustering has no effect).
	// // A clustered storage manager is NOT provided yet.
	// // Also you will have to take care of converting you data to
	// // and from binary format, since only
	// // array of bytes can be inserted in the index (see
	// // RTree::Node::load and RTree::Node::store for
	// // an example of how to do that).
	//
	// // tree.insertData(data.getBytes(), r, id);
	//
	// routeRTree.insertData(null, r, id); // main memory
	// // example of passing a null pointer as the associated data.
	// }
	//
	// long end = System.currentTimeMillis();
	//
	// // // System.err.println("Operations: " + count);
	// // System.err.println(tree);
	// // System.err.println("Minutes: " + ((end - start) / 1000.0f) /
	// // 60.0f);
	//
	// // since we created a new RTree, the PropertySet that was used to
	// // initialize the structure
	// // now contains the IndexIdentifier property, which can be used
	// // later to reuse the index.
	// // (Remember that multiple indices may reside in the same storage
	// // manager at the same time
	// // and every one is accessed using its unique IndexIdentifier).
	// Integer indexID = (Integer) ps2.getProperty("IndexIdentifier");
	// // System.err.println("Index ID: " + indexID);
	//
	// boolean ret = routeRTree.isIndexValid();
	// if (ret == false)
	// System.err.println("Structure is INVALID!");
	//
	// // flush all pending changes to persistent storage (needed since
	// // Java might not call finalize when JVM exits).
	// routeRTree.flush();
	// } catch (Exception e) {
	// e.printStackTrace();
	// }
	//
	// return routeRTree;
	// }

	private void printVertices(Graph graph) {
		Collection<GraphNode> vs = graph.getVertices();
		for (GraphNode v : vs) {
			System.out.println(v.getId() + ": " + v.getRouteIds());
		}
	}

	void printRoutes(HashMap<Integer, Route> routes) {
		Set<Integer> intSet = routes.keySet();
		for (Integer i : intSet) {
			System.out.println(routes.get(i));
		}
	}

}